package bishiqinagxun;

import java.util.ArrayList;

public class Test3 {
    //题目 ：笔试强训 day23  第三题 城市群的数量
    //算法 ：就是dfs 深搜  经典

    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        //就是一个dfs  深搜
        int n = m.size();  //矩阵的大小
        boolean[] flg = new boolean[n];  //用来标记 一下是否找过了
        int count = 0;  //记录一下  有多少个城市群
        for(int i  = 0; i < n;i++) {
            if(flg[i] == false) {
                count++;  //没找过 直接是一个城市群
                dfs(m,flg,n,i);
            }
        }
        return count;
    }
    private static void dfs(ArrayList<ArrayList<Integer>> m,boolean[] flg, int n,int i) {
        flg[i] = true;  //遍历过了就标记一下
        for(int j = 0; j < n;j++) {
            if(j != i && flg[j] == false && m.get(j).get(i) == 1) {
                dfs(m,flg,n,j);
            }
        }
    }
    public static void main(String[] args) {

    }
}
